#include <iostream>


#include <iostream>
#include <ctime>
#include <cassert>
#include <algorithm>
#include <typeinfo>
#include <cmath>

#include "TestSortHelper.h"

using namespace std;

template<typename Item>
class MaxHeap{
private:
    Item *data;
    int *indexes;

    int count;
    int capcity;

    void shiftUp(int p) {
        int k = p/2;
        while(k>=1 && data[indexes[p]]>data[indexes[k]]){
            swap(indexes[k],indexes[p]);
            p = k;
            k = p/2;
        }
    }

    void shiftDown(int k) {
        while(k*2<=count){
            int j = k*2;
            if(j+1<=count && data[indexes[j+1]]>data[indexes[j]]){
                j++;
            }
            if(data[indexes[j]]<data[indexes[k]]) break;
            swap(indexes[j],indexes[k]);
            k=j;
        }
    }
public:
    MaxHeap(int capacity){
        data = new Item[capacity+1];
        indexes = new int[capacity+1];
        count = 0;
        this->capcity = capacity;
    }

    ~MaxHeap(){
        delete[] data;
        delete[] indexes;
    }

    int size(){
        return count;
    }

    bool isEmpty(){
        return count == 0;
    }

    void insert(int idx, Item insert){
        assert(count<capcity);
        assert(idx>=0 && idx<capcity);

        data[++count] = insert;
        indexes[count]=idx+1;

        shiftUp(count);
    }

    void change(int idx,Item item){
        assert(idx>=0&&idx<count);
        data[idx+1] = item;

        for(int i = 1;i<=count;i++){
            if(indexes[i] == idx+1){
                shiftUp(i);
                shiftDown(i);
                return ;
            }
        }

    }

    bool contain(int k){
        return k<count;
    }

    void del(int k){

    }


    Item pop(){
        assert(count!=0);
        Item result = data[indexes[1]];
        swap(indexes[count],indexes[1]);
        count--;
        shiftDown(1);
        return result;
    }

    void print(){
        cout<<"array: ";
        for(int i = 0; i< count;i++){
            cout<<i+1<<" ";
        }
        cout<<endl;
        cout<<"index: ";
        for(int i = 0; i< count;i++){
            cout<<indexes[i+1]<<" ";
        }
        cout<<endl;
        cout<<"data: ";
        for(int i = 0; i< count;i++){
            cout<<data[i+1]<<" ";
        }
        cout<<endl;
    }
};

int main() {
    int n = 10;
    cout << "Test for Random Array, size = " << n << ", randome range [0, " << n << "]" << endl;
    int *arr1 = TestSortHelper::generateRandomArray(n, 0, n);

    MaxHeap<int> heap = MaxHeap<int>(n);
    for (int i = 0;i<n;i++){
        heap.insert(i,arr1[i]);
    }
    heap.print();
    heap.change(5,5);
    heap.print();
    for (int i = 0;i<n;i++){
        cout<<(heap.pop())<<" ";
    }
    cout<<endl;
}